package BHeap;

import static org.junit.Assert.*;
import org.junit.Before;
import org.junit.Ignore;
import org.junit.Test;

public class BHTimplTest {
	
	private BHTimpl<Integer> heap1;
	private BHTimpl<Integer> heap2;
	private final BHNode<Integer> NIL = new BHNode<Integer>();
	private BHNode<Integer> head;
	private final BHNode<Integer> NODE_VALOR_10 = new BHNode<Integer>(new Integer(10));
	private final BHNode<Integer> NODE_VALOR_11 = new BHNode<Integer>(new Integer(11));
	private final BHNode<Integer> NODE_VALOR_12 = new BHNode<Integer>(new Integer(12));
	private final BHNode<Integer> NODE_VALOR_14 = new BHNode<Integer>(new Integer(14));
	private final BHNode<Integer> NODE_VALOR_1000 = new BHNode<Integer>(new Integer(1000));
	private final BHNode<Integer> NODE_VALOR_0 = new BHNode<Integer>(new Integer(0));
	private final BHNode<Integer> NODE_VALOR_1 = new BHNode<Integer>(new Integer(1));
	private final BHNode<Integer> NODE_VALOR_2 = new BHNode<Integer>(new Integer(2));
	private final BHNode<Integer> NODE_VALOR_3 = new BHNode<Integer>(new Integer(3));
	private final BHNode<Integer> NODE_VALOR_4 = new BHNode<Integer>(new Integer(4));
	private final BHNode<Integer> NODE_VALOR_5 = new BHNode<Integer>(new Integer(5));
	private final BHNode<Integer> NODE_VALOR_6 = new BHNode<Integer>(new Integer(6));
	private final BHNode<Integer> NODE_VALOR_7 = new BHNode<Integer>(new Integer(7));
	private final BHNode<Integer> NODE_VALOR_8 = new BHNode<Integer>(new Integer(8));
	private final BHNode<Integer> NODE_VALOR_9 = new BHNode<Integer>(new Integer(9));
	private final Integer max = Integer.MAX_VALUE;
	private final Integer min = Integer.MIN_VALUE;
	@Before
	public void reiniciaHeap(){
		heap1 = new BHTimpl<Integer>();
		heap2 = new BHTimpl<Integer>();
		//heap.make_heap();
	}

	@Test
	public void test_make_heap(){
		heap1.insert(2);
		heap1.make_heap();
		assertEquals(NIL,heap1.getHead());
	}

	@Test
	public void testInsert(){
		
		assertTrue(heap1.getHead().isEmpty());
		heap1.insert(null);
		assertEquals(NIL, heap1.getHead());//ignorar insert(null)
		
		
		heap1.insert(new Integer(1));//NODE_VALOR_1

		/* Head
		 * data 	= 1 
		 * child 	= NIL
		 * sibling 	= NIL
		 * degree 	= 0
		**/
		/**		NIL
		 * 		|
		 * 		Head - NIL
		 *		|
		 *		NIL
		**/
		
		assertFalse(heap1.getHead().isEmpty());//heap1 nao esta mais vazia
		
		/**testando o head sem filho**/
		head = heap1.getHead();//ok
		assertEquals(0, head.getDegree());
		assertEquals(NIL, head.parent);//nao tera pai enquanto for HEAD ou irmao do HEAD
		assertEquals(new Integer(1), head.getData());
		assertEquals(NIL, head.getChild());//nao tem filho
		assertEquals(NIL, head.sibling);//nao tem irmao
		

		heap1.insert(new Integer(2));//NODE_VALOR_2
		/* Head
		 * data 	= 1 
		 * child 	= Filho1
		 * sibling 	= NIL
		 * degree 	= 1
		 * 
		 * Filho1
		 * data 	= 2
		 * child 	= NIL 
		 * sibling 	= NIL
		 * degree 	= 0
		**/
		/**			NIL
		 * 			|
		 * 			Head(1) - NIL
		 *			|
		 *		Filho1(2) - NIL
		 *		|
		 *		NIL
		**/
		
		/**testando o head com filho**/
		head = heap1.getHead();//ok
		assertEquals(1, head.getDegree());//Agr +1
		assertEquals(NIL, head.parent);//nao tera pai enquanto for HEAD ou irmao do HEAD
		assertEquals(new Integer(1), head.getData());
		assertEquals(NODE_VALOR_2/**Filho1**/, head.getChild());
		assertEquals(NIL, head.sibling);
		
		/**testando o 1o(e unico) filho do head**/
		BHNode<Integer> filho_do_head = heap1.getHead().getChild();//ok
		assertEquals(0, filho_do_head.getDegree());
		assertEquals(head, filho_do_head.parent);//filho do HEAD
		assertEquals(new Integer(2), filho_do_head.getData());
		assertEquals(NIL, filho_do_head.getChild());//folha
		assertEquals(NIL, filho_do_head.sibling);
		
		
	
		heap1.insert(new Integer(1000));//NODE_VALOR_1000
		/* Head
		 * data 	= 1000
		 * child 	= NIL
		 * sibling 	= exHead
		 * degree	= 0
		 * 
		 * Agr temos o exHead deslocado pra direita do seu sibling
		 * data 	= 1 
		 * child 	= Filho1 
		 * sibling 	= NIL
		 * degree 	= 1
		 * 
		 * Filho1<filho do exHead>
		 * data 	= 2 
		 * child 	= NIL
		 * sibling 	= NIL
		 * degree 	= 0
		**/
		/**		NIL  		 
		 * 		|		  	 
		 * 		Head(1000) - exHead(1) - NIL
		 *		|			 |
		 *		NIL		Filho1(2) - NIL
		 *				|
		 *				NIL
		**/	
		
		assertEquals(NODE_VALOR_1000, heap1.getHead());//trocou o Head
		
		/**testando o novoHead sem filho**/
		head = heap1.getHead();//ok
		assertEquals(0, head.getDegree());
		assertEquals(NIL, head.parent);//nao tera pai enquanto for HEAD ou irmao do HEAD
		assertEquals(new Integer(1000), head.getData());
		assertEquals(NIL, head.getChild());//nao tem filho
		assertEquals(NODE_VALOR_1/**exHead**/, head.sibling);
		
		/**testando o exHead(irmao do atual head) com 1filho**/
		BHNode<Integer> irmao_do_head = heap1.getHead().sibling;//ok
		assertEquals(1, irmao_do_head.getDegree());
		assertEquals(NIL, irmao_do_head.parent);//nao tera pai enquanto for HEAD ou irmao do HEAD
		assertEquals(new Integer(1), irmao_do_head.getData());
		assertEquals(NODE_VALOR_2/**Filho1**/, irmao_do_head.getChild());
		assertEquals(NIL, irmao_do_head.sibling);
		
		/**testando o 1o filho(e unico) do exHead, sobrinho do head**/
		BHNode<Integer> sobrinho_do_head = heap1.getHead().sibling.getChild();//ok
		assertEquals(0, sobrinho_do_head.getDegree());
		assertEquals(irmao_do_head, sobrinho_do_head.parent);
		assertEquals(new Integer(2), sobrinho_do_head.getData());
		assertEquals(NIL, sobrinho_do_head.getChild());//folha
		assertEquals(NIL, sobrinho_do_head.sibling);
		

		
		heap1.insert(new Integer(4));//NODE_VALOR_4
		/* Head
		 * data 	= 1000
		 * child 	= NIL
		 * sibling 	= exHead
		 * degree 	= 0
		 * 
		 * Agr temos o exHead deslocado pra filho do head
		 * data 	= 1
		 * child 	= Filho1
		 * sibling 	= NIL
		 * degree	= 1
		 * 
		 * Filho1<filho do exHead>
		 * data 	= 2 
		 * child 	= NIL
		 * sibling 	= NIL 
		 * degree 	= 0
		 * 
		 * QuartoNode
		 * data 	= 4
		 * child 	= NIL
		 * sibling 	= NIL
		 * degree 	= 0
		**/
		/**				NIL  	
		 * 				|		  	
		 * 				Head(1000) - NIL
		 *				|			
		 *			exHead(1) - QuartoNode(4) - NIL
		 *			|					|
		 *			Filho1(2) - NIL		NIL
		 *			|
		 *			NIL
		**/	
		
		/**testando o head com 2filhos**/
		head = heap1.getHead();//ok
		assertEquals(2, head.getDegree());//Agr +1
		assertEquals(NIL, head.parent);//nao tera pai enquanto for HEAD ou irmao do HEAD
		assertEquals(new Integer(1000), head.getData());
		assertEquals(NODE_VALOR_1/**exHead**/, head.getChild());//O filho com maior degree: o exHead = NODE_VALOR_1, degree = 1
		assertEquals(NIL, head.sibling);//nao tem +irmao
		
		/**testando o exHead(1o filho do atual head) com 1filho**/
		BHNode<Integer> filho1_do_head = heap1.getHead().getChild();//ok
		assertEquals(1, filho1_do_head.getDegree());
		assertEquals(head, filho1_do_head.parent);//primeiro filho do head
		assertEquals(new Integer(1), filho1_do_head.getData());
		assertEquals(NODE_VALOR_2/**Filho1**/,filho1_do_head.getChild());
		assertEquals(NODE_VALOR_4/**QuartoNode**/, filho1_do_head.sibling);	 
		
		/**testando o 1o filho(e unico) do exHead, neto do atual head**/
		BHNode<Integer> neto_do_head/**folha da arvore**/ = heap1.getHead().getChild().getChild();//ok	
		assertEquals(0, neto_do_head.getDegree());
		assertEquals(filho1_do_head, neto_do_head.parent);
		assertEquals(new Integer(2), neto_do_head.getData());
		assertEquals(NIL, neto_do_head.getChild());//folha
		assertEquals(NIL, neto_do_head.sibling);
		
		/**testando o 2o filho do head**/
		BHNode<Integer> filho2_do_head = heap1.getHead().getChild().sibling;//ok	
		
		assertEquals(0, filho2_do_head.getDegree());
		assertEquals(head, filho2_do_head.parent);//segundo filho do head
		assertEquals(new Integer(4), filho2_do_head.getData());
		assertEquals(NIL, filho2_do_head.getChild());
		assertEquals(NIL, filho2_do_head.sibling);
		
		
		for(int i = 0; i <= 10; i++){
			heap2.insert(new Integer(i));
		}
		
		/**		NIL	
		 * 		|		
		 * 		10	-	8	-	6
		 * 		|		|		|
		 * 		NIL		9 - NIL	2	-	4	-	7 - NIL
		 * 				|		|		|		|
		 * 				NIL		0-3-NIL	5 - NIL	NIL
		 * 						| | 	|
		 * 						1-NIL	NIL
		 * 						|
		 * 						NIL
		 **/
		
		assertEquals(NODE_VALOR_10, heap2.getHead());//trocou o Head
		
		/**testando o 10(head)**/
		BHNode<Integer> node_10 = heap2.getHead();//ok		
		assertEquals(0, node_10.getDegree());
		assertEquals(NIL, node_10.parent);
		assertEquals(new Integer(10), node_10.getData());
		assertEquals(NIL, node_10.getChild());
		assertEquals(NODE_VALOR_8, node_10.sibling);
		
		/**testando o 9**/
		BHNode<Integer> node_9 = heap2.getHead().sibling.getChild();//ok		
		assertEquals(0, node_9.getDegree());
		assertEquals(NODE_VALOR_8, node_9.parent);
		assertEquals(new Integer(9), node_9.getData());
		assertEquals(NIL, node_9.getChild());
		assertEquals(NIL, node_9.sibling);
		
		/**testando o 8**/
		BHNode<Integer> node_8 = heap2.getHead().sibling;//ok
		assertEquals(1, node_8.getDegree());
		assertEquals(NIL, node_8.parent);
		assertEquals(new Integer(8), node_8.getData());
		assertEquals(NODE_VALOR_9, node_8.getChild());
		assertEquals(NODE_VALOR_6, node_8.sibling);
		
		/**testando o 7**/
		BHNode<Integer> node_7 = heap2.getHead().sibling.sibling.getChild().sibling.sibling;//ok
		assertEquals(0, node_7.getDegree());
		assertEquals(NODE_VALOR_6, node_7.parent);
		assertEquals(new Integer(7), node_7.getData());
		assertEquals(NIL, node_7.getChild());
		assertEquals(NIL, node_7.sibling);
		
		/**testando o 6**/
		BHNode<Integer> node_6 = heap2.getHead().sibling.sibling;//ok	
		assertEquals(3, node_6.getDegree());
		assertEquals(NIL, node_6.parent);
		assertEquals(new Integer(6), node_6.getData());
		assertEquals(NODE_VALOR_2, node_6.getChild());
		assertEquals(NIL, node_6.sibling);
		
		/**testando o 5**/
		BHNode<Integer> node_5 = heap2.getHead().sibling.sibling.getChild().sibling.getChild();//ok	
		assertEquals(0, node_5.getDegree());
		assertEquals(NODE_VALOR_4, node_5.parent);
		assertEquals(new Integer(5), node_5.getData());
		assertEquals(NIL, node_5.getChild());
		assertEquals(NIL, node_5.sibling);
		
		/**testando o 4**/
		BHNode<Integer> node_4 = heap2.getHead().sibling.sibling.getChild().sibling;//ok
		assertEquals(1, node_4.getDegree());
		assertEquals(NODE_VALOR_6, node_4.parent);
		assertEquals(new Integer(4), node_4.getData());
		assertEquals(NODE_VALOR_5, node_4.getChild());
		assertEquals(NODE_VALOR_7, node_4.sibling);
		
		/**testando o 3**/
		BHNode<Integer> node_3 = heap2.getHead().sibling.sibling.getChild().getChild().sibling;//ok
		assertEquals(0, node_3.getDegree());
		assertEquals(NODE_VALOR_2, node_3.parent);
		assertEquals(new Integer(3), node_3.getData());
		assertEquals(NIL, node_3.getChild());
		assertEquals(NIL, node_3.sibling);
		
		/**testando o 2**/
		BHNode<Integer> node_2 = heap2.getHead().sibling.sibling.getChild();//ok
		assertEquals(2, node_2.getDegree());
		assertEquals(NODE_VALOR_6, node_2.parent);
		assertEquals(new Integer(2), node_2.getData());
		assertEquals(NODE_VALOR_0, node_2.getChild());
		assertEquals(NODE_VALOR_4, node_2.sibling);
		
		/**testando o 1**/
		BHNode<Integer> node_1 = heap2.getHead().sibling.sibling.getChild().getChild().getChild();//ok
		assertEquals(0, node_1.getDegree());
		assertEquals(NODE_VALOR_0, node_1.parent);
		assertEquals(new Integer(1), node_1.getData());
		assertEquals(NIL, node_1.getChild());
		assertEquals(NIL, node_1.sibling);
		
		/**testando o 0**/
		BHNode<Integer> node_0 = heap2.getHead().sibling.sibling.getChild().getChild();//ok
		assertEquals(1, node_0.getDegree());
		assertEquals(NODE_VALOR_2, node_0.parent);
		assertEquals(new Integer(0), node_0.getData());
		assertEquals(NODE_VALOR_1, node_0.getChild());
		assertEquals(NODE_VALOR_3, node_0.sibling);
	}

	@Test
	public void testGetHead(){
		assertTrue(heap1.getHead().isEmpty());
		
		/**		NIL
		 *		|
		 *		NIL(HEAD?)
		 * 		|
		 *		NIL
		**/
		
		BHNode<Integer> newHead = new BHNode<Integer>(1);
		heap1.setHead(newHead);
		
		/**		NIL
		 * 		|
		 * 		newHead - NIL
		 *		|
		 *		NIL
		**/
		
		assertFalse(heap1.getHead().isEmpty());
		assertEquals(newHead, heap1.getHead());
	}
	
	@Test
	public void testSetHead(){/**tbm testa os construtores de BHNode**/
		BHNode<Integer> newHead = new BHNode<Integer>(1);
		heap1.setHead(newHead );
		
		assertEquals(0, newHead.getDegree());
		assertEquals(null, newHead.parent);//nao tera pai enquanto for HEAD ou irmao do HEAD
		assertEquals(new Integer(1), newHead.getData());
		assertEquals(null, newHead.getChild());//nao tem filho
		assertEquals(null, newHead.sibling);//nao tem irmao ainda
		
		heap1.setHead(null);
		assertEquals(newHead, heap1.getHead());//ignorar setHead(null)
		
		heap1.setHead(NIL);
		assertFalse(heap1.getHead().isEmpty());
		assertEquals(newHead, heap1.getHead());//ignorar setHead(NIL)
		
		BHNode<Integer> newHead3 = new BHNode<Integer>(max);
		heap1.setHead(newHead3);
		assertEquals(0, newHead3.getDegree());
		assertEquals(null, newHead3.parent);//nao tera pai enquanto for HEAD ou irmao do HEAD
		assertEquals(max /**Valor maximo**/, newHead3.getData());
		assertEquals(null, newHead3.getChild());//nao tem filho
		assertEquals(null, newHead3.sibling);//nao tem irmao ainda
		
		BHNode<Integer> newHead4 = new BHNode<Integer>(min);
		heap1.setHead(newHead4);	
		assertEquals(0, newHead4.getDegree());
		assertEquals(null, newHead4.parent);//nao tera pai enquanto for HEAD ou irmao do HEAD
		assertEquals(min /**Valor minimo**/, newHead4.getData());
		assertEquals(null, newHead4.getChild());//nao tem filho
		assertEquals(null, newHead4.sibling);//nao tem irmao ainda
	}

	@Test
	public void testMinimum(){
		assertEquals(NIL,heap1.minimum());
		heap1.insert(new Integer(11));
		heap1.insert(new Integer(12));
		heap1.insert(new Integer(1000));
		heap1.insert(new Integer(14));
		assertEquals(NODE_VALOR_11,heap1.minimum());
		
		assertEquals(NIL,heap2.minimum());
		for(int i = 0; i <= 10; i++){
			heap2.insert(new Integer(i));
			assertEquals(NODE_VALOR_0,heap2.minimum());
		}
		assertEquals(NODE_VALOR_0,heap2.minimum());
	}

	@Ignore
	//quebra
	public void testExtract_mim(){
		assertEquals(NIL,heap1.minimum());
		heap1.insert(new Integer(11));
		heap1.insert(new Integer(12));
		heap1.insert(new Integer(1000));
		heap1.insert(new Integer(14));

		assertEquals(NODE_VALOR_11,heap1.minimum());
		
		System.out.println(heap1.minimum()+"aaaaaa");
		heap1.extract_mim();
		System.out.println(heap1.minimum()+"bbbbbbbb");
		

		/**			NIL  	
		 * 			|		  	
		 * 		  1000 - NIL
		 *			|			
		 *		 11(X) - 14 - NIL
		 *			|	 |
		 *			12 - NIL
		 *			|
		 *			NIL
		**/	
		assertEquals(NODE_VALOR_12,heap1.minimum());//fail
		assertEquals(NODE_VALOR_12,heap1.getHead());//??
		//System.out.println(heap1.getHead().sibling.getChild());
		
		assertEquals(NIL,heap2.minimum());
		for(int i = 0; i <= 10; i++){
			heap2.insert(new Integer(i));
			assertEquals(NODE_VALOR_0,heap2.minimum());
		}
	}
	
	@Test
	public void testUnion(){
		
		//tree1
		heap1.insert(new Integer(11));
		heap1.insert(new Integer(12));
		heap1.insert(new Integer(1000));
		heap1.insert(new Integer(14));
		/**			NIL  	
		 * 			|		  	
		 * 		  1000 - NIL
		 *			|			
		 *			11 - 14 - NIL
		 *			|	 |
		 *			12 - NIL
		 *			|
		 *			NIL
		**/	

		//tree2
		for(int i = 0; i <= 10; i++){
			heap2.insert(new Integer(i));
		}
		/**		NIL	
		 * 		|		
		 * 		10	-	8	-	6
		 * 		|		|		|
		 * 		NIL		9 - NIL	2	-	4	-	7 - NIL
		 * 				|		|		|		|
		 * 				NIL		0-3-NIL	5 - NIL	NIL
		 * 						| | 	|
		 * 						1-NIL	NIL
		 * 						|
		 * 						NIL
		 **/
		
		//GERA:
		/**		NIL	
		 * 		|		
		 * 		10	-	8	-	1000	-	6
		 * 		|		|		|			|
		 * 		NIL		9 - NIL	11-14-NIL	2	-	4	-	7 - NIL
		 * 				|		|  |		|		|		|
		 * 				NIL		12-NIL		0-3-NIL	5 - NIL	NIL
		 * 						|			| | 	|
		 * 						NIL			1-NIL	NIL
		 * 									|
		 * 									NIL
		 **/
		heap2.union(heap1);
		//heap1.union(heap2);
		
		/**testando o 10(head)**/
		BHNode<Integer> node_10 = heap2.search(10);	
		assertEquals(0, node_10.getDegree());
		assertEquals(NIL, node_10.parent);
		assertEquals(new Integer(10), node_10.getData());
		assertEquals(NIL, node_10.getChild());
		assertEquals(NODE_VALOR_8, node_10.sibling);
		
		/**testando o 9**/
		BHNode<Integer> node_9 = heap2.search(9);		
		assertEquals(0, node_9.getDegree());
		assertEquals(NODE_VALOR_8, node_9.parent);
		assertEquals(new Integer(9), node_9.getData());
		assertEquals(NIL, node_9.getChild());
		assertEquals(NIL, node_9.sibling);
		
		/**testando o 8**/
		BHNode<Integer> node_8 = heap2.search(8);
		assertEquals(1, node_8.getDegree());
		assertEquals(NIL, node_8.parent);
		assertEquals(new Integer(8), node_8.getData());
		assertEquals(NODE_VALOR_9, node_8.getChild());
		assertEquals(NODE_VALOR_1000, node_8.sibling);
		
		/**testando o 7**/
		BHNode<Integer> node_7 = heap2.search(7);
		assertEquals(0, node_7.getDegree());
		assertEquals(NODE_VALOR_6, node_7.parent);
		assertEquals(new Integer(7), node_7.getData());
		assertEquals(NIL, node_7.getChild());
		assertEquals(NIL, node_7.sibling);
		
		/**testando o 6**/
		BHNode<Integer> node_6 = heap2.search(6);	
		assertEquals(3, node_6.getDegree());
		assertEquals(NIL, node_6.parent);
		assertEquals(new Integer(6), node_6.getData());
		assertEquals(NODE_VALOR_2, node_6.getChild());
		assertEquals(NIL, node_6.sibling);
		
		/**testando o 5**/
		BHNode<Integer> node_5 = heap2.search(5);	
		assertEquals(0, node_5.getDegree());
		assertEquals(NODE_VALOR_4, node_5.parent);
		assertEquals(new Integer(5), node_5.getData());
		assertEquals(NIL, node_5.getChild());
		assertEquals(NIL, node_5.sibling);
		
		/**testando o 4**/
		BHNode<Integer> node_4 = heap2.search(4);
		assertEquals(1, node_4.getDegree());
		assertEquals(NODE_VALOR_6, node_4.parent);
		assertEquals(new Integer(4), node_4.getData());
		assertEquals(NODE_VALOR_5, node_4.getChild());
		assertEquals(NODE_VALOR_7, node_4.sibling);
		
		/**testando o 3**/
		BHNode<Integer> node_3 = heap2.search(3);
		assertEquals(0, node_3.getDegree());
		assertEquals(NODE_VALOR_2, node_3.parent);
		assertEquals(new Integer(3), node_3.getData());
		assertEquals(NIL, node_3.getChild());
		assertEquals(NIL, node_3.sibling);
		
		/**testando o 2**/
		BHNode<Integer> node_2 = heap2.search(2);
		assertEquals(2, node_2.getDegree());
		assertEquals(NODE_VALOR_6, node_2.parent);
		assertEquals(new Integer(2), node_2.getData());
		assertEquals(NODE_VALOR_0, node_2.getChild());
		assertEquals(NODE_VALOR_4, node_2.sibling);
		
		/**testando o 1**/
		BHNode<Integer> node_1 = heap2.search(1);
		assertEquals(0, node_1.getDegree());
		assertEquals(NODE_VALOR_0, node_1.parent);
		assertEquals(new Integer(1), node_1.getData());
		assertEquals(NIL, node_1.getChild());
		assertEquals(NIL, node_1.sibling);
		
		/**testando o 0**/
		BHNode<Integer> node_0 = heap2.search(0);
		assertEquals(1, node_0.getDegree());
		assertEquals(NODE_VALOR_2, node_0.parent);
		assertEquals(new Integer(0), node_0.getData());
		assertEquals(NODE_VALOR_1, node_0.getChild());
		assertEquals(NODE_VALOR_3, node_0.sibling);
		
		/**testando o 1000**/
		BHNode<Integer> node_1000 = heap2.search(1000);
		assertEquals(2, node_1000.getDegree());
		assertEquals(NIL, node_1000.parent);
		assertEquals(new Integer(1000), node_1000.getData());
		assertEquals(NODE_VALOR_11, node_1000.getChild());
		assertEquals(NODE_VALOR_6, node_1000.sibling);
		
		/**testando o 11**/
		BHNode<Integer> node_11 = heap2.search(11);
		assertEquals(1, node_11.getDegree());
		assertEquals(NODE_VALOR_1000, node_11.parent);
		assertEquals(new Integer(11), node_11.getData());
		assertEquals(NODE_VALOR_12, node_11.getChild());
		assertEquals(NODE_VALOR_14, node_11.sibling);
		
		/**testando o 12**/
		BHNode<Integer> node_12 = heap2.search(12);
		assertEquals(0, node_12.getDegree());
		assertEquals(NODE_VALOR_11, node_12.parent);
		assertEquals(new Integer(12), node_12.getData());
		assertEquals(NIL, node_12.getChild());
		assertEquals(NIL, node_12.sibling);
		
		/**testando o 14**/
		BHNode<Integer> node_14 = heap2.search(14);
		assertEquals(0, node_14.getDegree());
		assertEquals(NODE_VALOR_1000, node_14.parent);
		assertEquals(new Integer(14), node_14.getData());
		assertEquals(NIL, node_14.getChild());
		assertEquals(NIL, node_14.sibling);
	}

	@Ignore
	public void testDecrease_key(){
		
	}

	@Ignore
	public void testDelete(){
		
	}

	@Ignore
	public void testBinomial_link(){
		
	}
	
	@Test
	public void test_merge_binomial_heap(){
		//tree1
		heap1.insert(new Integer(11));
		heap1.insert(new Integer(12));
		heap1.insert(new Integer(1000));
		heap1.insert(new Integer(14));
		/**			NIL  	
		 * 			|		  	
		 * 		  1000 - NIL
		 *			|			
		 *			11 - 14 - NIL
		 *			|	|
		 *			12 - NIL
		 *			|
		 *			NIL
		**/	

		//tree2
		for(int i = 0; i <= 10; i++){
			heap2.insert(new Integer(i));
		}
		/**		NIL	
		 * 		|		
		 * 		10	-	8	-	6
		 * 		|		|		|
		 * 		NIL		9 - NIL	2	-	4	-	7 - NIL
		 * 				|		|		|		|
		 * 				NIL		0-3-NIL	5 - NIL	NIL
		 * 						| | 	|
		 * 						1-NIL	NIL
		 * 						|
		 * 						NIL
		 **/
		
		//GERA:
		/**		NIL	
		 * 		|		
		 * 		10	-  	1000	-	8	-	6
		 * 		|		|			|		|
		 * 		NIL		11-14-NIL 	9 - NIL	2	-	4	-	7 - NIL
		 * 				|  |		|		|		|		|
		 * 				12-NIL		NIL		0-3-NIL	5 - NIL	NIL
		 * 				|					| | 	|
		 * 				NIL					1-NIL	NIL
		 * 									|
		 * 									NIL
		 **/
		
		heap2.merge_binomial_heap(heap1);
		/**descomente e comente a anterior para testar o que o union modificou algo no merge**///heap2.union(heap1);
		
		/**testando o 10(head)**/
		BHNode<Integer> node_10 = heap2.search(10);	
		assertEquals(0, node_10.getDegree());
		assertEquals(NIL, node_10.parent);
		assertEquals(new Integer(10), node_10.getData());
		assertEquals(NIL, node_10.getChild());
		assertEquals(NODE_VALOR_1000, node_10.sibling);
		
		/**testando o 9**/
		BHNode<Integer> node_9 = heap2.search(9);		
		assertEquals(0, node_9.getDegree());
		assertEquals(NODE_VALOR_8, node_9.parent);
		assertEquals(new Integer(9), node_9.getData());
		assertEquals(NIL, node_9.getChild());
		assertEquals(NIL, node_9.sibling);
		
		/**testando o 8**/
		BHNode<Integer> node_8 = heap2.search(8);
		assertEquals(1, node_8.getDegree());
		assertEquals(NIL, node_8.parent);
		assertEquals(new Integer(8), node_8.getData());
		assertEquals(NODE_VALOR_9, node_8.getChild());
		assertEquals(NODE_VALOR_6, node_8.sibling);
		
		/**testando o 7**/
		BHNode<Integer> node_7 = heap2.search(7);
		assertEquals(0, node_7.getDegree());
		assertEquals(NODE_VALOR_6, node_7.parent);
		assertEquals(new Integer(7), node_7.getData());
		assertEquals(NIL, node_7.getChild());
		assertEquals(NIL, node_7.sibling);
		
		/**testando o 6**/
		BHNode<Integer> node_6 = heap2.search(6);	
		assertEquals(3, node_6.getDegree());
		assertEquals(NIL, node_6.parent);
		assertEquals(new Integer(6), node_6.getData());
		assertEquals(NODE_VALOR_2, node_6.getChild());
		assertEquals(NIL, node_6.sibling);
		
		/**testando o 5**/
		BHNode<Integer> node_5 = heap2.search(5);	
		assertEquals(0, node_5.getDegree());
		assertEquals(NODE_VALOR_4, node_5.parent);
		assertEquals(new Integer(5), node_5.getData());
		assertEquals(NIL, node_5.getChild());
		assertEquals(NIL, node_5.sibling);
		
		/**testando o 4**/
		BHNode<Integer> node_4 = heap2.search(4);
		assertEquals(1, node_4.getDegree());
		assertEquals(NODE_VALOR_6, node_4.parent);
		assertEquals(new Integer(4), node_4.getData());
		assertEquals(NODE_VALOR_5, node_4.getChild());
		assertEquals(NODE_VALOR_7, node_4.sibling);
		
		/**testando o 3**/
		BHNode<Integer> node_3 = heap2.search(3);
		assertEquals(0, node_3.getDegree());
		assertEquals(NODE_VALOR_2, node_3.parent);
		assertEquals(new Integer(3), node_3.getData());
		assertEquals(NIL, node_3.getChild());
		assertEquals(NIL, node_3.sibling);
		
		/**testando o 2**/
		BHNode<Integer> node_2 = heap2.search(2);
		assertEquals(2, node_2.getDegree());
		assertEquals(NODE_VALOR_6, node_2.parent);
		assertEquals(new Integer(2), node_2.getData());
		assertEquals(NODE_VALOR_0, node_2.getChild());
		assertEquals(NODE_VALOR_4, node_2.sibling);
		
		/**testando o 1**/
		BHNode<Integer> node_1 = heap2.search(1);
		assertEquals(0, node_1.getDegree());
		assertEquals(NODE_VALOR_0, node_1.parent);
		assertEquals(new Integer(1), node_1.getData());
		assertEquals(NIL, node_1.getChild());
		assertEquals(NIL, node_1.sibling);
		
		/**testando o 0**/
		BHNode<Integer> node_0 = heap2.search(0);
		assertEquals(1, node_0.getDegree());
		assertEquals(NODE_VALOR_2, node_0.parent);
		assertEquals(new Integer(0), node_0.getData());
		assertEquals(NODE_VALOR_1, node_0.getChild());
		assertEquals(NODE_VALOR_3, node_0.sibling);
		
		/**testando o 1000**/
		BHNode<Integer> node_1000 = heap2.search(1000);
		assertEquals(2, node_1000.getDegree());
		assertEquals(NIL, node_1000.parent);
		assertEquals(new Integer(1000), node_1000.getData());
		assertEquals(NODE_VALOR_11, node_1000.getChild());
		assertEquals(NODE_VALOR_8, node_1000.sibling);
		
		/**testando o 11**/
		BHNode<Integer> node_11 = heap2.search(11);
		assertEquals(1, node_11.getDegree());
		assertEquals(NODE_VALOR_1000, node_11.parent);
		assertEquals(new Integer(11), node_11.getData());
		assertEquals(NODE_VALOR_12, node_11.getChild());
		assertEquals(NODE_VALOR_14, node_11.sibling);
		
		/**testando o 12**/
		BHNode<Integer> node_12 = heap2.search(12);
		assertEquals(0, node_12.getDegree());
		assertEquals(NODE_VALOR_11, node_12.parent);
		assertEquals(new Integer(12), node_12.getData());
		assertEquals(NIL, node_12.getChild());
		assertEquals(NIL, node_12.sibling);
		
		/**testando o 14**/
		BHNode<Integer> node_14 = heap2.search(14);
		assertEquals(0, node_14.getDegree());
		assertEquals(NODE_VALOR_1000, node_14.parent);
		assertEquals(new Integer(14), node_14.getData());
		assertEquals(NIL, node_14.getChild());
		assertEquals(NIL, node_14.sibling);
	}
	
	@Test
	public void testSearch(){
		assertEquals(NIL,heap1.search(6));//vazia
		heap1.insert(new Integer(1));//add NODE_VALOR_1
		heap1.insert(new Integer(2));//add NODE_VALOR_2
		heap1.insert(new Integer(1000));//add NODE_VALOR_1000
		heap1.insert(new Integer(4));//add NODE_VALOR_4
		
		assertEquals(NIL,heap1.search(3));
		
		assertEquals(NODE_VALOR_1,heap1.search(1));
		assertEquals(NODE_VALOR_2,heap1.search(2));
		assertEquals(NODE_VALOR_1000,heap1.search(1000));
		assertEquals(NODE_VALOR_4,heap1.search(4));
		
		assertEquals(NIL,heap1.search(null));
		assertEquals(NIL,heap1.search(min));
		assertEquals(NIL,heap1.search(max));
		
		int inicio = 1;
		int fim = 90;
		/**sacanagem, fica o dia todo kkkk**///for(int i = min; i < max; i++){
		for(int i = inicio; i < fim; i++){
			heap2.insert(new Integer(i));
		}
		for(int i = inicio; i < fim; i++){
			assertEquals(new BHNode<Integer>(new Integer(i)),heap2.search(i));
			if(i!=1 && i!=2 && i!=4){
				assertEquals(NIL,heap1.search(i));
			}
		}
	}
}